package 学习计划.数据结构;

/**
 * @author 会玩的洋洋
 * https://leetcode.cn/problems/increasing-triplet-subsequence/?envType=study-plan&id=shu-ju-jie-gou-ji-chu&plan=data-structures&plan_progress=cqjfoh6https://leetcode.cn/problems/increasing-triplet-subsequence/?envType=study-plan&id=shu-ju-jie-gou-ji-chu&plan=data-structures&plan_progress=cqjfoh6
 */
public class _334_递增的三元子序列 {
    /**
     * 执行用时：8ms，内存消耗：89.2MB
     * @param nums
     * @return
     */
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        int[] leftMin = new int[n], rightMax = new int[n];
        leftMin[0] = nums[0];
        rightMax[n - 1] = nums[n - 1];
        for (int i = 1; i < n; i++) {
            leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
        }
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
        }

        for (int i = 1; i < n - 1; i++)  {
            if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {
                return true;
            }
        }
        return false;
    }

    /**
     * 执行用时：2ms，内存消耗：91.5MB
     * @param nums
     * @return
     */
    public boolean increasingTriplet2(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        int first = nums[0], second = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            if (nums[i] > second) {
                return true;
            } else if (nums[i] > first) {
                second = nums[i];
            } else {
                first = nums[i];
            }
        }
        return false;
    }

}
